ff1588d761d55f48f61a52249e1dcc24

<!DOCTYPE html>

<title>Lowest Common Ancestor</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Lowest Common Ancestor</span></h1>

</header>

</div>

<p>Als <b>Lowest Common Ancestor</b> oder <b>Least Common Ancestor</b> (<b>LCA</b>), deutsch <i>„letzter gemeinsamer <a href="Out-Tree#Vorfahr" title="Out-Tree">Vorfahre</a>“</i>, wird in der <a href="Informatik" title="Informatik">Informatik</a> und <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> ein Ermittlungskonzept bezeichnet, das einen gegebenen gewurzelten <a href="Bin%C3%A4rbaum" title="Binärbaum">Baum von Datenstrukturen</a> effizient vorverarbeitet, sodass anschließend Anfragen nach dem letzten gemeinsamen Vorfahren für beliebige Knotenpaare in konstanter Zeit beantwortet werden können.

</p><p>Bäume gehören zu den fundamentalen Datenstrukturen der Informatik. Sie werden häufig verwendet, um Daten in einer hierarchischen oder geschachtelten Struktur darzustellen. Zwei klassische Beispiele sind Such- und Entscheidungsbäume. Algorithmische Standardfragen für Bäume sind zum Beispiel die Pre-, Post- und Inordertraversierung.

Ein in diesem Kontext weniger bekanntes algorithmisches Problem ist die Suche nach dem letzten gemeinsamen Vorfahren (LCA).<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition_des_LCA">Definition des LCA</h2></div>

<p>Gegeben sei ein Baum <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T=(V,E)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d92d5a4adcb93751dbecb1cddfc0a254b9488f9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.141ex; height:2.843ex;" alt="{\displaystyle T=(V,E)}" loading="lazy"></span> mit einem Wurzelknoten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"></span>, insgesamt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Knoten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (|V|=n)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (|V|=n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9c5f96fc4ee3e863ebb50b5c50fad0b572b1b264.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.383ex; height:2.843ex;" alt="{\displaystyle (|V|=n)}" loading="lazy"></span> und einer Höhe <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"></span>. Der Lowest Common Ancestor (LCA) zweier Knoten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"></span> ist derjenige Knoten, der ein Elternknoten von sowohl <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"></span> als auch <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"></span> ist und am weitesten von der Wurzel <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"></span> entfernt liegt, also die größtmögliche Tiefe besitzt.

</p><p>Ziel ist es, einen gegebenen Baum <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"></span> effizient so vorzuverarbeiten, dass LCA <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eadf12294edccd7a29c99cfc1765e4a14bf47e58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.301ex; height:2.843ex;" alt="{\displaystyle (u,v)}" loading="lazy"></span> Anfragen möglichst schnell beantwortet werden können.

</p>

<div class="mw-heading mw-heading2"><h2 id="Entwicklung_(Geschichte)"><span id="Entwicklung_.28Geschichte.29"></span>Entwicklung (Geschichte)</h2></div>

<p>Das LCA-Problem wurde 1973 erstmals von <a href="Alfred_Aho" class="mw-redirect" title="Alfred Aho">Alfred Aho</a>, <a href="John_Hopcroft" class="mw-redirect" title="John Hopcroft">John Hopcroft</a> und <a href="Jeffrey_Ullman" title="Jeffrey Ullman">Jeffrey Ullman</a> definiert.

</p><p>Im Jahre 1984 entwickelten Dov Harel und <a href="Robert_Tarjan" title="Robert Tarjan">Robert Tarjan</a> die erste effiziente Datenstruktur zur Lösung des LCA-Problems. Dabei wird der Eingabebaum in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"></span> (siehe <a href="Landau-Symbole" title="Landau-Symbole">Landau-Symbole</a>) vorverarbeitet, so dass die Abfragen in konstanter Zeit, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(1)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5aeb15c854068604d35a2dd82a925899fafd3690.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.822ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)}" loading="lazy"></span> beantwortet werden können. Allerdings gilt die Datenstruktur als sehr komplex und schwierig zu implementieren. Tarjan fand später einen einfacheren, wenn auch weniger effizienten Algorithmus, der auf der <a href="Union-Find-Struktur" title="Union-Find-Struktur">Union-Find-Struktur</a> basiert und den LCA aus einer vorher berechneten Menge von Knotenpaaren ermittelt (Tarjan’s Offline Least Common Ancestor Algorithm (TOLCA)). Im Jahre 1988 vereinfachten Baruch Schieber und Uzi Vishkin diese Datenstruktur, so dass diese implementierbar wurde und dennoch einen Vorverarbeitungsaufwand von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"></span> Zeit und einen Abfrageaufwand von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(1)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5aeb15c854068604d35a2dd82a925899fafd3690.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.822ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)}" loading="lazy"></span> aufweist.

</p><p>1993 entdeckten Omer Berkman und Uzi Vishkin einen neuen Weg, das LCA-Problem mit Hilfe von Reduktion und <a href="Range_Minimum_Query" title="Range Minimum Query">Range Minimum Query (RMQ)</a> zu lösen. Der Zeitaufwand hat auch hier lineare Vorverarbeitungszeit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"></span> und konstante Abfragezeit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(1)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5aeb15c854068604d35a2dd82a925899fafd3690.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.822ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)}" loading="lazy"></span>. Dieser Lösungsansatz wurde 2000 von <a href="Michael_Bender" class="mw-disambig" title="Michael Bender">Michael Bender</a> und Martin Farach-Colton vereinfacht.<sup id="cite_ref-Bender2000_2-0" class="reference"><a href="#cite_note-Bender2000-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Anwendungsgebiete">Anwendungsgebiete</h2></div>

<p>Die LCA-Ermittlung kann angewendet werden, um den LCA (Last common ancestor, auch <a href="Most_recent_common_ancestor" title="Most recent common ancestor">Most recent common ancestor</a>, MRCA) von <a href="Phylogenetischer_Baum" title="Phylogenetischer Baum">Gen-Bäumen</a> (<a href="Bioinformatik" title="Bioinformatik">Bioinformatik</a>) zu ermitteln.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Verallgemeinerung">Verallgemeinerung</h2></div>

<p>Ursprünglich wurde der Begriff des LCA im Zusammenhang mit Bäumen untersucht, doch kann er auch für <a href="Gerichteter_azyklischer_Graph" class="mw-redirect" title="Gerichteter azyklischer Graph">gerichtete azyklische Graphen</a> (<span style="font-style:normal;font-weight:normal"><a href="Englische_Sprache" title="Englische Sprache">englisch</a></span> <span lang="en-Latn" style="font-style:italic">directed acyclic graphs</span>, DAGs) definiert werden. Dabei wird davon ausgegangen, dass die Kanten des DAG von den Eltern zu den Kindern führen. Die ursprüngliche Definition von Aït-Kaci <i>et al.</i> (1989)<sup id="cite_ref-Ait1998_5-0" class="reference"><a href="#cite_note-Ait1998-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> wurde von Bender <i>et al.</i> (2005) vereinfacht.<sup id="cite_ref-Bender2005_6-0" class="reference"><a href="#cite_note-Bender2005-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.it-cow.de/post/Ermittlung-des-Lowest-Common-Ancestors-mithilfe-des-RMQ-Algorithmus-WIP.aspx">Ermittlung des Lowest Common Ancestors mithilfe des RMQ-Algorithmus</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://www.mi.fu-berlin.de/inf/groups/ag-ti/theses/bachelor_finished/kresse_antonia/index.html"><i>Effiziente Berechnung vom letzten gemeinsamen Vorfahren und Anwendungen – FU Berlin</i></a>. Auf: fu-berlin.de – abgerufen am 22. Januar 2023</span>

</li>

Michael A. Bender, Martin Farach-Colton: <i>The LCA problem revisited.</i> In: <i>Proceedings of the 4th Latin American Symposium on Theoretical Informatics.</i> Serie: <i>Lecture Notes in Computer Science</i>, Band 1776, Springer-Verlag, 2000, ISBN 978-3-540-67306-4, S. 88–94; <a href="https://doi.org/10.1007/10719839_9" class="extiw external" title="doi:10.1007/10719839 9">doi:10.1007/10719839_9</a> (<a href="Englische_Sprache" title="Englische Sprache">englisch</a>).</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://page.mi.fu-berlin.de/alt/vorlesungen/sem09/Algorithmen%20zum%20Ermitteln%20des%20Lowest%20Common%20Ancestor_M2.pdf"><i>Algorithmen zum Ermitteln des Lowest Common Ancestor (LCA) – FU Berlin</i></a> (PDF, 638 kB) fu-berlin.de – abgerufen am 10. März 2013</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a></span> <span class="reference-text"><span class="cite">Jana Hertel, Peter F. Stadler: <a rel="nofollow" class="external text" href="https://www.bioinf.uni-leipzig.de/publications/supplements/15-037"><i>BIOINF 15-037: The Expansion of Animal MicroRNA Families Revisited.</i></a> In: <i>bioinf.uni-leipzig.de.</i> Bioinformatics Leipzig,<span class="Abrufdatum"> abgerufen am 22. Januar 2023</span> (englisch).</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3ALowest+Common+Ancestor&rft.title=BIOINF+15-037%3A+The+Expansion+of+Animal+MicroRNA+Families+Revisited&rft.description=BIOINF+15-037%3A+The+Expansion+of+Animal+MicroRNA+Families+Revisited&rft.identifier=https%3A%2F%2Fwww.bioinf.uni-leipzig.de%2Fpublications%2Fsupplements%2F15-037&rft.creator=Jana+Hertel%2C+Peter+F.+Stadler&rft.publisher=Bioinformatics+Leipzig&rft.language=en"> </span></span>

</li>

H. Aït-Kaci, R. Boyer, P. Lincoln, R. Nasr: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Efficient implementation of lattice operations</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">ACM Transactions on Programming Languages and Systems</cite>. 11. Jahrgang, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>1</span>, 1989, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>115–146</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1145/59287.59293">10.1145/59287.59293</a></span> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Lowest+Common+Ancestor&rft.atitle=Efficient+implementation+of+lattice+operations&rft.au=H.%26%2332%3BA%C3%AFt-Kaci%2C%26%2332%3BR.%26%2332%3BBoyer%2C%26%2332%3BP.%26%2332%3BLincoln%2C+...&rft.date=1989&rft.doi=10.1145%2F59287.59293&rft.genre=journal&rft.issue=1&rft.jtitle=ACM+Transactions+on+Programming+Languages+and+Systems&rft.pages=115-146&rft.volume=11.+Jahrgang" style="display:none"> </span></span>

</li>

Michael A. Bender, Martín Farach-Colton, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Lowest common ancestors in trees and directed acyclic graphs</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Journal of Algorithms</cite>. 57. Jahrgang, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>2</span>, 2005, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>75–94</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1016/j.jalgor.2005.08.001">10.1016/j.jalgor.2005.08.001</a></span> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Lowest+Common+Ancestor&rft.atitle=Lowest+common+ancestors+in+trees+and+directed+acyclic+graphs&rft.au=Michael+A.%26%2332%3BBender%2C%26%2332%3BMart%C3%ADn%26%2332%3BFarach-Colton%2C%26%2332%3BGiridhar%26%2332%3BPemmasani%2C+...&rft.date=2005&rft.doi=10.1016%2Fj.jalgor.2005.08.001&rft.genre=journal&rft.issue=2&rft.jtitle=Journal+of+Algorithms&rft.pages=75-94&rft.volume=57.+Jahrgang" style="display:none"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-12-04" href="https://de.wikipedia.org/wiki/?title=Lowest_Common_Ancestor&oldid=262130292">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>